package com.huangkailong.leetcode;

import java.util.*;

/**
 * @author huangkl
 * @date 2021-06-21 12:06
 */

/**
 * 给你一个链表数组，每个链表都已经按升序排列。<br/>
 * <br/>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。<br/>
 * <br/>
 * <br/>
 * <br/>
 * 示例 1：<br/>
 * <br/>
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]<br/>
 * 输出：[1,1,2,3,4,4,5,6]<br/>
 * 解释：链表数组如下：<br/>
 * [<br/>
 *   1->4->5,<br/>
 *   1->3->4,<br/>
 *   2->6<br/>
 * ]<br/>
 * 将它们合并到一个有序链表中得到。<br/>
 * 1->1->2->3->4->4->5->6<br/>
 * 示例 2：<br/>
 * <br/>
 * 输入：lists = []<br/>
 * 输出：[]<br/>
 * 示例 3：<br/>
 * <br/>
 * 输入：lists = [[]]<br/>
 * 输出：[]<br/>
 * <br/>
 * <br/>
 * 提示：<br/>
 * <br/>
 * k == lists.length<br/>
 * 0 <= k <= 10^4<br/>
 * 0 <= lists[i].length <= 500<br/>
 * -10^4 <= lists[i][j] <= 10^4<br/>
 * lists[i] 按 升序 排列<br/>
 * lists[i].length 的总和不超过 10^4<br/>
 * <br/>
 */
public class MergeKLists {
    /**
     * 优先队列
     */
    public ListNode solution1(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }

        Queue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparing(l -> l.val));
        for (int i = 0; i < lists.length; i++) {
            if(lists[i] == null){
                continue;
            }
            priorityQueue.offer(lists[i]);
        }

        ListNode root = null;
        ListNode p = null;
        while (!priorityQueue.isEmpty()){
            ListNode listNode = priorityQueue.poll();
            if(Objects.isNull(root)){
                p = root = listNode;
            }else {
                p.next = listNode;
                p = listNode;
            }
            if(Objects.nonNull(listNode.next)){
                priorityQueue.offer(listNode.next);
            }
        }
        return root;
    }

    /**
     * 归并
     */
    public ListNode solution2(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        if(lists.length == 1){
            return lists[0];
        }
        return doSolution2(lists);
    }

    /**
     * 循环遍历
     */
    public ListNode solution3(ListNode[] lists){
        if(lists == null || lists.length == 0){
            return null;
        }
        if(lists.length == 1){
            return lists[0];
        }
        ListNode p = null;
        for (ListNode list : lists) {
            p = merge(p, list);
        }

        return p;
    }

    public ListNode doSolution2(ListNode[] lists){
        if(lists.length == 1){
            return lists[0];
        }else if(lists.length == 2){
            return merge(lists[0], lists[1]);
        }else {
            int length = lists.length;
            int mid = length / 2;
            ListNode l = doSolution2(Arrays.copyOfRange(lists, 0, mid));
            ListNode r = doSolution2(Arrays.copyOfRange(lists, mid, length));
            return merge(l, r);
        }
    }

    public ListNode merge(ListNode l1, ListNode l2){
        if(l1 == null){
            return l2;
        }

        if(l2 == null){
            return l1;
        }

        ListNode root = null;
        ListNode l1p = l1;
        ListNode l2p = l2;
        ListNode p = null;
        ListNode min;
        while (l1p != null && l2p != null){
            if(l1p.val > l2p.val){
                min = l2p;
                l2p = l2p.next;
            }else {
                min = l1p;
                l1p = l1p.next;
            }

            if(root == null){
                root = p = min;
            }else {
                p.next = min;
                p = min;
            }
        }

        if(l1p != null){
            p.next = l1p;
        }
        if(l2p != null){
            p.next = l2p;
        }

        return root;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}


